/*
 *  Librarie de tipuri de date abstracte (TDA)
 
    Copyright (C) 2007  Catedra de Structuri de Date

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
/**
 @file graph.h
 @author Florin Pop
 @brief This header file contains structures and functions needed to work
 with graphs (orineted or non-oriented).

 It contains functions for creating a graph, destroying it and some elementary
 algorithms. 
 */

#include "linkedlist.h"

#ifndef GRAPH_H_
#define GRAPH_H_

struct graph_adt;
struct graph_link;
struct graph_node;

/**
@brief Structure representing a graph.

The structure contains a field that represent the number of nodes in graph and a pointer
to the nodes list.
@see See also: G_New(), G_Free()
*/
typedef struct graph_adt *Graph;

/**
@brief Structure representing a node in a graph.

The structure contains ...
EDIT (Andrei Bucur): Obligatoriu: cheia si costul
//TODO
*/
typedef struct graph_node *GraphNode;

/**
@brief 
*/
typedef struct graph_link *GraphLink;

/**
@brief Creates a new graph, with no nodes.

The function creates a graph structure and reserves memory for it.
The graph do not contains node. No link between nodes is created.
*/
Graph G_New();

/**
@brief Destroys the specified graph.

Memory used by the graph as well as all elements is freed. Thus, trying
to access the data in a destroyed graph (e.g. through a pointer) will most likely
result in a Access violation / segfault.

@param graph the graph to be destroyed. A \c Graph structure.
*/
void G_Free(Graph graph);

/**
@brief Returns the number of nodes in graph.

The function returns the number of nodes in the specified graph. Note
that the function returns the value of the \a count element. Thus, directly
modifying the \a count structure member will lead to inaccurate results.

@param graph graph whose number of nodes is to be returned.
@return the number of nodes in the graph.
*/
unsigned int G_GetNodeCount(Graph graph);

/**
@brief Returns the node in graph specified by index.

The function returns a certain node in the specified graph. 

@param graph graph that contains (or not) the specified node.
@return the specified node or NULL if it does not exist
*/
GraphLink G_GetNode(Graph graph, unsigned int index);

/**
@brief
*/
unsigned int G_GetEdgeCount(Graph graph);

/**
@brief Determines if the graph is empty (has no nodes), or not.

In fact the function returns the value of the <tt>nr_nodes == 0</tt> expression.
Thus, directly modifying the \a nr_nodes structure member will lead to inaccurate
results.

@param graph graph to be tested.
@return 1 if the graph is empty (no nodes), 0 otherwise.
*/
int G_IsEmpty(Graph graph);

/**
@brief Inserts a node in a graph.

The function adds the node specified by the \a n identifier. 
A new node is created and the number of nodes in the graph is increased by 1.

@param graph the graph in which to add the node.
@param n identifier specifying the node to be added.
*/
void G_AddNode(Graph graph, unsigned int n, double cost);

/**
@brief Removes a node from the graph.

The function removes the node specified by the \a n identifier. 
The number of nodes in the graph is decreased by 1.

@param graph the graph from which to remove the node.
@param n identifier specifying the node to be removed.
*/
void G_DelNode(Graph graph, unsigned int n);

/**
@brief Adds a new link in the graph.

The function adds a link in the graph between two nodes specified by the \a u and \a v identificators.
It also sets the cost of this link to the value specified by the \a cost identifier.

@param graph the graph in which to add the link.
@param u identifier specifying the first end of the link.
@param v identifier specifying the second end of the link.
@param cost identifier specifying the cost of the link.
*/
void G_AddLink(Graph graph, unsigned int u, unsigned int v, double cost);

/**
@brief Removes a link from the graph.

The function removes from the graph the link between the two nodes specified by the \a u and \a v identificators.

@param graph the graph from which to remove the link.
@param u identifier specifying the first end of the link.
@param v identifier specifying the second end of the link.
*/
void G_DelLink(Graph graph, unsigned int u, unsigned int v);

/**
@brief Tests if there is a link between two nodes of the graph.

The function tests to see if there is a link between the two nodes in the graph specified by the \a u and \a v identificators.

@param graph the graph in which to add the link.
@param u identifier specifying the first end of the link.
@param v identifier specifying the second end of the link.
@return 1 if there is a link between the two nodes, 0 otherwise.
*/
int G_IsLink(Graph graph, unsigned int u, unsigned int v);

/**
@brief Calculates the inner degree of a node in the graph.

The function calculates the inner degree of the node in the graph specified by the \a n identifier.

@param graph the graph which is supposed to contain the nodes specified.
@param n identifier specifying the node that will have its inner degree calculated.
@return a value greater than or equal to 0, which represents the inner degree of the node.
*/
unsigned int G_InnerDegree(Graph graph, unsigned int n);

/**
@brief Calculates the outer degree of a node in the graph.

The function calculates the outer degree of the node in the graph specified by the \a n identifier.

@param graph the graph which is supposed to contain the node specified.
@param n identifier specifying the node that will have its outer degree calculated.
@return a value greater than or equal to 0, which represents the outer degree of the node.
*/
unsigned int G_OuterDegree(Graph graph, unsigned int n);

/**
@brief Calculates the degree (inner + outer degree) of a node in the graph.

The function calculates the degree of the node in the graph specified by the \a n identifier.

@param graph the graph which is supposed to contain the node specified.
@param n identifier specifying the node that will have its degree calculated.
@return a value greater than or equal to 0, which represents the degree of the node.
*/
unsigned int G_Degree(Graph graph, unsigned int n);

/**
@brief Prints the nodes of the graph.

@param graph the graph that will have its nodes printed.
*/
void G_PrintNodes(Graph graph);

/**
@brief Prints the edges of the graph.

@param graph the graph that will have its edges printed.
*/
void G_PrintEdges(Graph graph);

/**
@brief Prints the connected components of the graph.

@param graph the graph that will have its connected components printed.
*/
void G_PrintConnectedComponent(Graph graph);

/**
@brief Prints the nodes of the graph and the neigbbours of each node (null if none).

@param graph the graph the function works on.
*/
void G_Print(Graph graph);

/**
@brief Calculates the number of connected components in the graph.

@param graph the graph which will have its number of connected components calculated.
@return a value greater than or equal to 0 (if the graph is NULL), which represents the number of connected components in the graph.
*/
unsigned int G_GetConnectedComponentCount(Graph graph);

/**
@brief Breadth First Search of the graph.

The function applies the BFS algorithm to the graph. The start node is specified by the \a source identifier.
In the end this function will have calculated an array of parents for each "visited" node, specified by the \a parent identifier,
and an array of distances from each node "visited" node to the source node.
Note that this algorithm only "visits" the nodes which are part of the same connected component of the graph as the source node.

@param graph the graph upon which the BFS algorithm is applied.
@param source identifier specifying the start node for the BFS algorithm.
@param parent identifier specifying the parent array.
@param distance identifier specifying the distance array.
*/
void G_BFS(Graph graph, unsigned int source, unsigned int *parent, unsigned int *distance);

/**
@brief Depth First Search of the graph.

The function applies the DFS algorithm to the graph. It calculates an array of parents for each "visited" node, specified by 
the \a parent identifier, an array of start times (the time when a node is "discovered") specified by the \a start_time 
identifier and an arrtay of finish times (the time when a node has no more neighbours the DFS algorithm can "visit"), 
specified by the \a end_time identifier.
Note that this algorithm "visits" the nodes in all the connected components of the graph (in other words, it "visits" all the
nodes of the graph).

@param graph the graph upon which the DFS algorithm is applied.
@param parent identifier specifying the parent array.
@param start_time identifier specifying the start times array.
@param end_time identifier specifying the finish times array.
*/
void G_DFS(Graph graph, unsigned int *parent, unsigned int *start_time, unsigned int *end_time);

/**
@brief It sorts the graph topologically, if possible (if the graph has no cycles).

The function sorts the graph topologically by building an array, specified by the \a top_sort identifier, which contains
the nodes of the graph in the reverse order of the finish times which are obtained when applying the DFS algorithm to the 
graph. The node with the highest finish time will be the first component of the array and the node with the lowest finish
time will be the last component of the array.

@param graph the graph to be topologically sorted.
@param top_sort identifier specifying the topological sort array.
@return 1 if the graph can be topologically sorted, 0 otherwise.
*/
int G_TopSort(Graph graph, unsigned int *top_sort);

/**
@brief Determines the Strongly Connected Components of the graph, if any.

The start node is specified by the \a start_node identifier. The \a list identifier
represents a linked list that will have other linked lists as its components. Each component
of the main linked list will therefore be a SCC of the graph.

@param graph the graph that will have its SCCs determined.
@param start_node identifier specifying the start node.
@param list identifier specifying a linked list of linked lists used to represent the SCCs of the graph.
*/
void G_SCC(Graph graph, unsigned int start_node, LinkedList list); 

/**
@brief Determines the Articulation Points of the graph, if any.

The \a cut_vertex identifier represents an array that will contain these articulation points.

@param graph the graph that will have its APs determined.
@param cut_vertex identifier specifying an array used to represent the APs of the graph.
@return the number of articulation points in the graph (0 if none).
*/
unsigned int G_AP(Graph graph, unsigned int *cut_vertex);

/**
@brief Determines the Bridges of the graph, if any.

The \a list identifier represents a linked list that will have other linked lists as its components. 
Each component of the main linked list will have anly two components, representing the first and the second end
of the bridge.

@param graph the graph that will have its SCCs determined.
@param list identifier specifying the linked list of linked lists used to represent the Bridges of the graph.
*/
void G_BR(Graph graph, LinkedList list);

/**
@brief Splits the graph into its biconex components, by deleteing all bridges. 
All nodes including articulation points are left unchanged.

@param graph the graph
@return the number of connected components in the graph.
*/
unsigned int G_BiConex(Graph graph);


/**
@brief Determines the shortest path from a source node to all other nodes for a directed graph with non negative link costs.

The function determines the distances from the sorce node to all nodes of the graph. 
The start node is specified by the \a s identifier. The \a d identifier represents 
a list with all the distances.

@param graph the graph to be analysed.
@param s identifier specifying the source node.
@param d identifier specifying the list that will contain the distances between the source node and all the other nodes.

@return 1 if all nodes can be reached from the source node, 0 otherwise.
*/
int G_Dijkstra(Graph graph, int s, double *d);

/**
@brief Determines the shortest path from a source node for a directed graph where some of the link costs may be negative.

The function determines the distances from the sorce node to all nodes of the graph.
Dijkstra's algorithm resolves the same problem with a lower running time, but requires
link costs to be non-negative.
The start node is specified by the \a s identifier. The \a dx identifier represents 
a list with all the distances.

@param graph the graph to be analysed.
@param s identifier specifying the source node.
@param dx identifier specifying the list that will contain the distances between the source node and all the other nodes.

@return 1 if there aren't any negative costs cycles, 0 otherwise.

*/
int G_BellmanFord(Graph graph, int s, double *dx);

/**
@brief Finds a subset of the links that forms a graph that includes all nodes and 
where the total cost of all the links is minimum.

The function finds a subset of links from a graph.This subset forms a graph that includes all 
the nodes from the original graph and where the total cost of the links is minimum.
The subset is given to the user as a list of parents specified by the \a p identifier 
for each node of the graph.

@param graph the graph to be analysed.
@param p represents the parent list of all nodes

@return the total cost of the found subset edges 
*/
double G_Kruskal(Graph graph, int *p);

/**
@brief Finds a subset of the links of a graph starting from a source node that forms a graph
that includes all nodes and where the total cost of all the edges is minimum.

The function finds a subset of links from a graph. The subset is build starting from a
source node gived by the \a s identifier.
This subset forms a graph that includes all the nodes from the original graph and where
the total cost of the links is minimum. The subset is given to the user as a list of 
parents specified by the \a p identifier for each node of the graph.

@param graph the graph to be analysed.
@param s identifier specifying the source node.
@param p represents the parent list of all nodes

@return the total cost of the found subset edges or -1 if the graph is not connected
*/
double G_Prim(Graph graph, int s, int *p);

/**
@brief Calculates the minimum cost of a path form i to j for all nodes i,j in the graph.

@param graph the graph
@param fw a pointer where the result is hold; fw[i][j] represents the minmum cost for pair of nodes (i,j).
*/
void G_FloydWarshall(Graph graph, double **fw);

/**
@brief Calculates the maximum flow from source to destination using FordFulkerson algorithm.

@param graph the graph wich represents the network
@param source the source node
@param destination the destination node
*/
double G_FordFulkerson(Graph graph, unsigned int source, unsigned int destination);

#endif /*GRAPH_H_*/
